from collections import deque


# 迪杰斯特拉算法只适用于有向无环图，并且各个边的权值全为正数


class DAG:
    def __init__(self):
        self.direct_acyclic_graph = {}
        self.vertex_set = set()

    def add_edge(self, from_vertex, to_vertex, weight):
        self.direct_acyclic_graph[(from_vertex, to_vertex)] = weight
        self.vertex_set.add(from_vertex)
        self.vertex_set.add(to_vertex)
        return self

    def __find_lowest_cost(self, costs, processed):
        lowest_cost = float('inf')
        lowest_cost_vertex = None
        for k, v in costs.items():
            if v[0] < lowest_cost and k not in processed:
                lowest_cost = v[0]
                lowest_cost_vertex = k
        return lowest_cost_vertex

    def dijkstra(self, start_vertex, end_vertex):
        if start_vertex not in self.vertex_set or end_vertex not in self.vertex_set:
            return None
        costs = {node[1]: (float('inf'), None) for node in self.direct_acyclic_graph.keys()}  # 存储当前的结点，代价以及父节点
        processed = []
        costs[start_vertex] = (0, None)
        node = self.__find_lowest_cost(costs, processed)
        while node is not None:  # 若节点全部访问过则返回None
            cost = costs[node][0]  # 当前结点的最短路径
            neighbors = [i[1] for i in self.direct_acyclic_graph.keys() if i[0] == node]  # 相邻的结点
            for neighbor in neighbors:
                new_cost = cost + self.direct_acyclic_graph[(node, neighbor)]  # 计算新的代价
                if costs[neighbor][0] > new_cost:
                    costs[neighbor] = (new_cost, node)  # 如果有更低的代价则进行修改
            processed.append(node)
            node = self.__find_lowest_cost(costs, processed)  # 寻找未查找的下一个权值最小的节点
        path = deque([end_vertex])
        p = costs[end_vertex][1]
        while p is not None:
            path.appendleft(p)
            p = costs[p][1]
        return list(path), costs[end_vertex][0]  # 返回路径以及代价
